K-means Clustering

주어진 데이터를

k

개의 cluster로 묶는 알고리즘.

각 cluster와 Distance차이의 Variance를 최소화하는 방식으로 동작한다.

각 cluster의 중심(Centroid, mean)와 cluster 내의 element와의 거리의 제곱합을 cost function으로 하여, 이 function value를 최소화하는 방향으로 각 element들의 소속 cluster를 업데이트한다.

algorithm

$K$ : 원하는 클러스터의 개수

$z_{i}^{t}$ : $i$ 번째 클러스터에 $t$ 번째 데이터 $x^{t}$ 가 속함: (1 or 0: one-hot vector). 알려지지 않고, 추정해야 되는 대상이므로 Latent Variable이 된다.

Mean Vector $μ_{k}$ ( $1 \leq k \leq K$ )를 초기화한다.
1. Random하게 초기화
2. PCA를 통해 얻은 가장 Variance가 큰 eigenvector 축에 대해 $k$ 등분.
3. 최적의 $k$ 는, $k$ 를 증가 시켜 가면서 clustering error가 잘 떨어지지 않는 시점으로 한다.
모든 Data point $x^{t}$ 에 대해 만약 $k$ 번째 클러스터가, $x^{t}$ 와 $μ_{k}$ 간의 distance function value가 제일 작다면, $i = k$ 에 대해 $z_{i}^{t} = 1$ , 아니라면 0
각 $k$ 에 대해 $μ_{k} = \frac{t \sum z _{k}^{t} x ^{t}}{t \sum z _{k}^{t}}$
2, 3번 과정을 converge 할 때까지 반복한다.

위 과정은, MVN [[EM]] algorithm과 상당히 동일하며 EM algorithm 역시 Clustering algorithm의 일종이므로 연관이 있어 보인다.

[[../../../Mathematics/Probability/Distribution/Multivariate Distribution/MVN]] EM algorithm(GMM(guassian mixture model))은, K-means algorithm에서

모든 Prior( $π_{k}$ )가 동일함.
Covaraince Matrix $Σ_{k} = I$ 가 모두 Identity Matrix.
distance function을 n2 norm, Identity Matrix임을 제외하고 생각하면 Mahalonobis distance.
hard-방식의 $z_{i}^{t}$ 와 같은 cluster에 속하는지 여부를 $w_{k}^{t}$ 의 각 cluster에 속할지에 대한 확률 기반의 soft방식. 로 변환하였을때 거의 유사하다고 볼 수 있다.

이 때, EM algorithm이 반복됨에 따라 Likelihood가 증가한다는 점에 기반하면 K-means Algorithm 역시 반복됨에 따라 Likelihood가 증가함을 알 수 있다.

EM과 비슷하므로, Semi-parametic method에 기반해 density를 estimation 가능하다.

ar g θ max P (D ∣ θ) = ar g θ max t \prod P (x^{t}, z^{t} ∣ θ) = ar g θ max t \prod P (x^{t} ∣ z^{t}, θ) P (z^{t} ∣ θ) = ar g θ max t \sum [lo g P (x^{t} ∣ z^{t}, θ) + lo g P (z^{t} ∣ θ)]

즉, 마찬가지로 log likelihood가 최대가 될 때를 구한다.

$p (x) = k = 1 \sum K N (x ∣ μ_{k}, Σ_{k}) P (g_{k})$

$P (g_{k}) = \frac{t \sum z _{k}^{t}}{N}$
$μ_{k} = \frac{\sum _{t} z _{k}^{t} x ^{t}}{\sum _{t} z _{k}^{t}}$
$Σ_{k} = \frac{\sum _{t} z _{k}^{t} ( x ^{t} - μ _{k} ) ( x ^{t} - μ _{k} ) ^{⊤}}{\sum _{t} z _{k}^{t}}$